0721. 账户合并【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 并查集

1. 📝 题目描述

• leetcode

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

---

示例 1：

输入：
accounts = [
  ["John", "johnsmith@mail.com", "john00@mail.com"],
  ["John", "johnnybravo@mail.com"],
  ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
  ["Mary", "mary@mail.com"]
]

输出：
[
  ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
  ["John", "johnnybravo@mail.com"],
  ["Mary", "mary@mail.com"]
]

解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "johnsmith@mail.com"。
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案
[
  ["Mary", "mary@mail.com"],
  ["John", "johnnybravo@mail.com"],
  ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"]
]
也是正确的。

示例 2：

输入：
accounts = [
  ["Gabe", "Gabe0@m.co", "Gabe3@m.co", "Gabe1@m.co"],
  ["Kevin", "Kevin3@m.co", "Kevin5@m.co", "Kevin0@m.co"],
  ["Ethan", "Ethan5@m.co", "Ethan4@m.co", "Ethan0@m.co"],
  ["Hanzo", "Hanzo3@m.co", "Hanzo1@m.co", "Hanzo0@m.co"],
  ["Fern", "Fern5@m.co", "Fern1@m.co", "Fern0@m.co"]
]

输出：
[
  ["Ethan", "Ethan0@m.co", "Ethan4@m.co", "Ethan5@m.co"],
  ["Gabe", "Gabe0@m.co", "Gabe1@m.co", "Gabe3@m.co"],
  ["Hanzo", "Hanzo0@m.co", "Hanzo1@m.co", "Hanzo3@m.co"],
  ["Kevin", "Kevin0@m.co", "Kevin3@m.co", "Kevin5@m.co"],
  ["Fern", "Fern0@m.co", "Fern1@m.co", "Fern5@m.co"]
]

---

提示：

• 1 <= accounts.length <= 1000
• 2 <= accounts[i].length <= 10
• 1 <= accounts[i][j].length <= 30
• accounts[i][0] 由英文字母组成
• accounts[i][j] (for j > 0) 是有效的邮箱地址

2. 🎯 s.1 - 并查集

c

// 简化实现：使用数组并查集，邮箱编号映射
#define MAXE 10001

int par[MAXE];

int find(int x) {
    while (par[x] != x) x = par[x] = par[par[x]];
    return x;
}

void unite(int a, int b) {
    par[find(a)] = find(b);
}

char** accountsMerge(char*** accounts, int accountsSize, int* accountsColSize, int* returnSize, int** returnColumnSizes) {
    // 统计所有邮箱并编号
    char* emails[MAXE];
    int emailCount = 0;
    int emailId[MAXE]; // accounts[i] 的每个邮箱的 id
    // 简化：直接用序号作为并查集索引
    for (int i = 0; i < MAXE; i++) par[i] = i;

    // 收集所有邮箱
    for (int i = 0; i < accountsSize; i++) {
        for (int j = 1; j < accountsColSize[i]; j++) {
            // 查找是否已存在
            int id = -1;
            for (int k = 0; k < emailCount; k++) {
                if (strcmp(emails[k], accounts[i][j]) == 0) { id = k; break; }
            }
            if (id == -1) { id = emailCount; emails[emailCount++] = accounts[i][j]; }
            // 将同一账户的邮箱合并
            if (j > 1) {
                int prevId = -1;
                for (int k = 0; k < emailCount; k++) {
                    if (strcmp(emails[k], accounts[i][1]) == 0) { prevId = k; break; }
                }
                unite(id, prevId);
            }
        }
    }

    // 按根分组
    int groups[MAXE][100];
    int groupSize[MAXE];
    memset(groupSize, 0, sizeof(groupSize));
    for (int i = 0; i < emailCount; i++) {
        int r = find(i);
        groups[r][groupSize[r]++] = i;
    }

    // 构建结果
    *returnSize = 0;
    char** result[MAXE];
    int resultColSize[MAXE];
    for (int i = 0; i < emailCount; i++) {
        if (groupSize[i] == 0) continue;
        // 查找 name
        char* name = NULL;
        for (int a = 0; a < accountsSize && !name; a++) {
            for (int j = 1; j < accountsColSize[a]; j++) {
                if (strcmp(accounts[a][j], emails[groups[i][0]]) == 0) {
                    name = accounts[a][0]; break;
                }
            }
        }
        // 排序邮箱
        for (int a = 0; a < groupSize[i] - 1; a++)
            for (int b = a + 1; b < groupSize[i]; b++)
                if (strcmp(emails[groups[i][a]], emails[groups[i][b]]) > 0) {
                    int tmp = groups[i][a]; groups[i][a] = groups[i][b]; groups[i][b] = tmp;
                }
        int cnt = groupSize[i] + 1;
        result[*returnSize] = (char**)malloc(sizeof(char*) * cnt);
        result[*returnSize][0] = name;
        for (int j = 0; j < groupSize[i]; j++)
            result[*returnSize][j + 1] = emails[groups[i][j]];
        resultColSize[*returnSize] = cnt;
        (*returnSize)++;
    }

    char*** res = (char***)malloc(sizeof(char**) * (*returnSize));
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; i++) {
        res[i] = result[i];
        (*returnColumnSizes)[i] = resultColSize[i];
    }
    return res;
}

js

/**
 * @param {string[][]} accounts
 * @return {string[][]}
 */
var accountsMerge = function (accounts) {
  const parent = new Map()
  const find = (x) => {
    if (!parent.has(x)) parent.set(x, x)
    while (parent.get(x) !== x) {
      parent.set(x, parent.get(parent.get(x)))
      x = parent.get(x)
    }
    return x
  }
  const union = (a, b) => parent.set(find(a), find(b))

  const emailToName = new Map()
  for (const acc of accounts) {
    const name = acc[0]
    for (let i = 1; i < acc.length; i++) {
      emailToName.set(acc[i], name)
      union(acc[1], acc[i])
    }
  }

  const groups = new Map()
  for (const email of emailToName.keys()) {
    const root = find(email)
    if (!groups.has(root)) groups.set(root, [])
    groups.get(root).push(email)
  }

  const res = []
  for (const [root, emails] of groups) {
    emails.sort()
    res.push([emailToName.get(root), ...emails])
  }
  return res
}

py

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        parent = {}
        def find(x):
            parent.setdefault(x, x)
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        def union(a, b):
            parent[find(a)] = find(b)

        email_to_name = {}
        for acc in accounts:
            name = acc[0]
            for email in acc[1:]:
                email_to_name[email] = name
                union(acc[1], email)

        groups = defaultdict(list)
        for email in email_to_name:
            groups[find(email)].append(email)

        return [[email_to_name[root]] + sorted(emails) for root, emails in groups.items()]

• 时间复杂度：$O(n\times l\times \alpha (n))$，其中 n 是邮箱总数，l 是邮箱平均长度
• 空间复杂度：$O(n\times l)$

算法思路：

• 用并查集合并同一账户的邮箱，同时记录邮箱到用户名的映射
• 将同一账户中的所有邮箱与第一个邮箱合并
• 最后按根分组，排序后输出